package org.flint.data.structure.leetcode;

import org.flint.data.structure.sgt.Merge;
import org.flint.data.structure.sgt.SegmentTree;

/**
 * @author flint92
 */
public class NumArray {

    private final SegmentTree<Integer> sgt;


    public NumArray(int[] nums) {
        int len;
        final Merge<Integer> merge = (a, b) -> a + b;
        if (nums == null || (len = nums.length) == 0) {
            sgt = new SegmentTree<>(new Integer[0], merge);
        } else {
            Integer[] data = new Integer[len];
            for (int i = 0; i < len; i++) {
                data[i] = nums[i];
            }
            sgt = new SegmentTree<>(data, merge);
        }
    }


    /**
     * Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
     * <p>
     * Example:
     * Given nums = [-2, 0, 3, -5, 2, -1]
     * <p>
     * sumRange(0, 2) -> 1
     * sumRange(2, 5) -> -1
     * sumRange(0, 5) -> -3
     * Note:
     * You may assume that the array does not change.
     * There are many calls to sumRange function.
     *
     * @param i     区间左边界
     * @param j     区间右边界
     * @return      区间值
     */
    public int sumRange(int i, int j) {
        return sgt.query(i, j);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 0, 3, -5, 2, -1};
        NumArray numArray = new NumArray(nums);
        assert 1 == numArray.sumRange(0, 2);
        assert -1 == numArray.sumRange(0, 5);
        assert -3 == numArray.sumRange(2, 5);
    }

}
